package exam2013;

/**
 * Sorted linked set (elements are unique and {@link Comparable})
 * @param <E> Elements' type
 */
public class SortedLinkedSet<E extends Comparable<E>> {
	
	/**
	 * Node of the internal linked list
	 */
	private class Node {
		E element;
		Node next;
		public Node(E el, Node nx) {
			element = el;
			next = nx;
		}
	}
	
	/**
	 * Reference to the first node
	 */
	private Node head = null;
	
	/**
	 * Elements/nodes count
	 */
	private int size = 0;
	
	
	/**
	 * Creates an empty set. 
	 * This constructor doesn't throw any {@link Exception}.
	 */
	public SortedLinkedSet() {
		return;
	}
	
	/**
	 * Creates a pre-populated set
	 * @param data Data to be sorted
	 * @throws DuplicateElementException Quite explicit, huh?
	 */
	public SortedLinkedSet(E... data) throws DuplicateElementException {
		for (E d: data)
			add(d);
	}
	
	/**
	 * Inserts an element at the right position using {@link Comparable#compareTo(Object)}
	 * @param element Element to be inserted
	 * @throws DuplicateElementException If a duplicate is found
	 */
	public void add(E element) throws DuplicateElementException {
		if (head == null)
			//easy case
			head = new Node(element, null);
		else {
			for (Node p=head, pr=null; p!=null; pr=p, p=p.next) {
				int c = element.compareTo(p.element);
				if (c < 0) {
					if (pr == null)
						//before head
						head = new Node(element, p);
					else
						//before p
						pr.next = new Node(element, p);
					break;
				}
				else if (c == 0)
					throw new DuplicateElementException(element.toString());
				//don't forget adding it if p is the last node
				if (p.next == null) {
					p.next = new Node(element, null);
					break; //avoid an infinite loop
				}
			}
		}
		//bonus counter
		size++;
	}
	
	/**
	 * Returns the number of elements in this sorted list
	 * @return number of elements in this sorted list
	 */
	public int size() {
		return size;
	}
	
	/**
	 * Mimics ArrayList's implementation
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder("["); //don't use '['!
		for (Node p=head; p!=null; /*manually done*/) {
			sb.append(p.element.toString());
			p = p.next;
			if (p != null)
				sb.append(','); //only if it's needed...
		}
		return sb.append(']').toString();
	}
	
	
	/**
	 * Sorts command-line arguments using this class
	 * @param args Strings to be sorted
	 */
	public static void main(String[] args) {
		SortedLinkedSet<String> sls = new SortedLinkedSet<>();
		//populate the set
		for (String a: args) {
			try {
				sls.add(a);
			}
			catch (DuplicateElementException e) {
				System.out.println("Duplicate: "+e.getMessage());
			}
		}
		//display info
		System.out.println("Data: "+sls);
		System.out.println("Size: "+sls.size());
	}
	
}
